Transactions on Combinatorics
Volume:12 Issue: 3, Sep 2023

Let $g_{k}(n)$ denote the number of sequences $t_{1},ldots,t_{n}$ in $\{0, 1,\ldots,k-1\}$ such that $t_{j+1}\equiv t_{j}-1, t_{j}$ or $t_{j}+1$ (mod $k$), $1\leq j\leq n$, (where $t_{n+1}$ is identified with $t_{1}$). It is proved combinatorially that $g_{4}(n)= 3^{n}+2+(-1)^{n}$ and $g_{6}(n)= 3^{n}+2^{n+1}+(-1)^{n}$. This solves a problem from Richard P. Stanley's 1986 text, $Enumerative$ $Combinatorics$.

Let $G$ be a simple connected graph of order $n$ with $m$ edges. Denote by $% \gamma _{1}^{+}\geq \gamma _{2}^{+}\geq \cdots \geq \gamma _{n}^{+}\geq 0$ the normalized signless Laplacian eigenvalues of $G$. In this work, we define the normalized signless Laplacian Estrada index of $G$ as $NSEE\left(G\right) =\sum_{i=1}^{n}e^{\gamma _{i}^{+}}.$ Some lower bounds on $%NSEE\left( G\right) $ are also established.

We first prove that there always exists a maximal rectangularly dualizable graph for a given rectangularly dualizable graph and present an algorithm for its construction. Further, we show that a maximal rectangularly dualizable graph can always be transformed to an edge-irreducible rectangularly dualizable graph and present an algorithm that transforms a maximal rectangularly dualizable graph to an edge-irreducible rectangularly dualizable graph.

The energy of a graph $G$, denoted by $\mathcal{E}(G)$, is defined as the sum of absolute values of all eigenvalues of $G$. A graph $G$ is called reciprocal if $ \frac{1}{\lambda} $ is an eigenvalue of $G$ whenever $\lambda$ is an eigenvalue of $G$. Further, if $ \lambda $ and $\frac{1}{\lambda}$ have the same multiplicities, for each eigenvalue $\lambda$, then it is called strong reciprocal. In (MATCH Commun. Math. Comput. Chem. 83 (2020) 631--633), it was conjectured that for every graph $G$ with maximum degree $\Delta(G)$ and minimum degree $\delta(G)$ whose adjacency matrix is non-singular, $\mathcal{E}(G) \geq \Delta(G) + \delta(G)$ and the equality holds if and only if $G$ is a complete graph. Here, we prove the validity of this conjecture for some strong reciprocal graphs. Moreover, we show that if $G$ is a strong reciprocal graph, then $\mathcal{E}(G) \geq \Delta(G) + \delta(G) - \frac{1}{2}$. Recently, it has been proved that if $G$ is a reciprocal graph of order $n$ and its spectral radius, $\rho$, is at least $4\lambda_{min}$, where $ \lambda_{min}$ is the smallest absolute value of eigenvalues of $G$, then $\mathcal{E}(G) \geq n+\frac{1}{2}$. In this paper, we extend this result to almost all strong reciprocal graphs without the mentioned assumption.

Let $G$ be a graph and $r\in\mathbb{N}$. The matching Kneser graph $\textsf{KG}(G, rK_2)$ is a graph whose vertex set is the set of $r$-matchings in $G$ and two vertices are adjacent if their corresponding matchings are edge-disjoint. In [M. Alishahi and H. Hajiabolhassan, On the Chromatic Number of Matching Kneser Graphs, Combin. Probab. and Comput., 29, No. 1 (2020), 1--21] it was conjectured that for any connected graph $G$ and positive integer $r\geq 2$, the chromatic number of $\textsf{KG}(G, rK_2)$ is equal to $|E(G)|-\textsf{ex}(G,rK_2)$, where $\textsf{ex}(G,rK_2)$ denotes the largest number of edges in $G$ avoiding a matching of size $r$. In this note, we show that the conjecture is not true for snarks.